#pragma once
#include <iostream>
#include <assert.h>

namespace ys
{
	template<class T>
	struct ListNode
	{
		T _data = T();
		ListNode* _prev = nullptr;
		ListNode* _next = nullptr;
	};

	template<class T, class Ref, class Ptr>
	class Iterator
	{
	public:
		typedef T value_type;
		typedef ListNode<value_type> Node;
		typedef Iterator<value_type, Ref, Ptr> self;
		Iterator(Node* node)
			:_node(node)
		{}

		bool operator!=(const self& node)
		{
			return _node != node._node;
		}
		Ref operator*()
		{
			return _node->_data;
		}
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator++(int)
		{
			_node = _node->_next;
			return *this;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		Node* _node;
	};

	template<class T, class Ref, class Ptr>
	class ReverseIterator
	{
	public:
		typedef T value_type;
		typedef ListNode<value_type> Node;
		typedef ReverseIterator<value_type, Ref, Ptr> self;
		ReverseIterator(Node* node)
			:_node(node)
		{}

		bool operator!=(const self& node)
		{
			return _node != node._node;
		}
		Ref operator*()
		{
			return _node->_data;
		}
		self& operator++()
		{
			_node = _node->_prev;
			return *this;
		}
		self& operator++(int)
		{
			_node = _node->_prev;
			return *this;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		Node* _node;
	};

	template<class T>
	class list
	{
	public:
		typedef T value_type; 
		typedef ListNode<value_type> Node;

		typedef Iterator<T, T&, T*> iterator;
		typedef Iterator<T, const T&, const T*> const_iterator;

		typedef ReverseIterator<T, T&, T*> reverse_iterator;
		typedef ReverseIterator<T, const T&, const T*> const_reverse_iterator;
		//------------------Member functions--------------------
		list()
			:_head(new Node())
			,_size(0)
		{
			_head->_next = _head;
			_head->_prev = _head;
		}
		list(const list<T>& lt)
			:_head(new Node())
			, _size(0)
		{
			_head->_next = _head;
			_head->_prev = _head;
			const_iterator cit = lt.cbegin();
			while (cit != lt.cend())
			{
				push_back(*cit);
			}
		}
		/*list<T>& operator=(const list<T>& lt)
		{
			list<T> tmp(lt);
			std::swap(_head, tmp._head);
			return *this;
		}*/
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		//--------------------Iterators:------------------------
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}

		const_iterator cbegin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator cend() const
		{
			return const_iterator(_head);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(_head->_prev);
		}
		reverse_iterator rend()
		{
			return reverse_iterator(_head);
		}

		const_reverse_iterator rcbegin() const
		{
			return const_reverse_iterator(_head->_prev);
		}
		const_reverse_iterator rcend() const
		{
			return const_reverse_iterator(_head);
		}
		//--------------------Capacity:-------------------------
		size_t size() const
		{
			return _size;
		}
		bool empty() const
		{
			return _head->_next == _head;
		}

		//--------------------Modifiers:------------------------
		void push_back(const value_type& val)
		{
			/*Node* newNode = new Node;
			newNode->_data = val;
			
			Node* prev = _head->_prev;

			newNode->_prev = prev;
			newNode->_next = _head;
			prev->_next = newNode;
			_head->_prev = newNode;

			++_size;*/
			insert(iterator(_head), val);
		}

		void pop_back()
		{
			/*assert(!empty());
			Node* node = _head->_prev;

			Node* prev = node->_prev;
			prev->_next = _head;
			_head->_prev = prev;

			node->_next = nullptr;
			node->_prev = nullptr;

			delete[] node;
			--_size;*/
			erase(iterator(_head->_prev));
		}

		void push_front(const value_type& val)
		{
			/*Node* newNode = new Node;
			newNode->_data = val;
			
			Node* next = _head->_next;

			_head->_next = newNode;
			next->_prev = newNode;
			newNode->_next = next;
			newNode->_prev = _head;

			_size++;*/
			insert(iterator(_head->_next), val);
		}

		void pop_front()
		{
			/*assert(!empty());
			Node* node = _head->_next;

			Node* next = node->_next;
			_head->_next = next;
			next->_prev = _head;

			node->_next = nullptr;
			node->_prev = nullptr;
		
			delete[] node;
			--_size;*/
			erase(iterator(_head->_next));
		}

		//插入的位置在pos前面
		iterator insert(iterator pos, const value_type& val)
		{
			Node* newNode = new Node;
			newNode->_data = val;

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur;

			prev->_next = newNode;
			next->_prev = newNode;
			newNode->_prev = prev;
			newNode->_next = next;

			++_size;
			return iterator(newNode);
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* next = pos._node->_next;
			Node* prev = pos._node->_prev;

			next->_prev = prev;
			prev->_next = next;

			pos._node->_next = nullptr;
			pos._node->_prev = nullptr;

			delete pos._node;

			--_size;
			return iterator(next);
		}

		void clear()
		{
			while (!empty())
			{
				pop_back();
			}
		}

		void swap(list<value_type>& lt)
		{
			std::swap(_head, lt._head);
		}
	private:
		Node* _head;
		size_t _size;
	};

	template<class T>
	void PrintList(const list<T>& lt)
	{
		typename list<T>::const_iterator cit = lt.cbegin();
		while (cit != lt.cend())
		{
			std::cout << *cit << " ";
			cit++;
		}
		std::cout << std::endl;
	}

	template<class Container>
	void PrintContainer(const Container& con)
	{
		typename Container::const_iterator cit = con.cbegin();
		while (cit != con.cend())
		{
			std::cout << *cit << " ";
			cit++; 
		}
		std::cout << std::endl;
	}
}